Cos'è crivello di eratostene?
Crivello di Eratostene
Il crivello di Eratostene è un algoritmo semplice e antico per trovare tutti i numeri primi fino a un limite specificato. Prende il nome dal matematico greco Eratostene di Cirene, vissuto nel III secolo a.C.
Come funziona:
- Crea una lista: Inizia creando una lista di tutti i numeri interi da 2 fino al limite desiderato (n).
- Identifica il primo numero primo: Il primo numero nella lista è 2, che è il primo numero primo.
- Elimina i multipli: Cancella dalla lista tutti i multipli di 2 (4, 6, 8, 10, ecc.) fino a n. Questi numeri non sono primi.
- Passa al numero successivo: Trova il numero successivo nella lista che non è stato cancellato. Questo numero è il prossimo numero primo.
- Ripeti: Ripeti i passaggi 3 e 4, cancellando tutti i multipli del nuovo numero primo trovato.
- Termina: Continua fino a quando il quadrato del numero primo corrente è maggiore di n. A questo punto, tutti i numeri rimanenti nella lista sono numeri primi.
Esempio:
Per trovare i numeri primi fino a 30:
- Lista: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
- Primo numero primo: 2
- Elimina i multipli di 2: 2 3
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
- Prossimo numero primo: 3
- Elimina i multipli di 3: 2 3 5 7
9 11 13 15 17 19 21 23 25 27 29
- Prossimo numero primo: 5
- Elimina i multipli di 5: 2 3 5 7 11 13
15 17 19 21 23 25 27 29
- Prossimo numero primo: 7
- Elimina i multipli di 7: 2 3 5 7 11 13 17 19
21 23 27 29
A questo punto, 7<sup>2</sup> = 49 > 30, quindi l'algoritmo termina. I numeri primi inferiori a 30 sono: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Complessità:
Il crivello di Eratostene ha una complessità temporale di O(n log log n), dove n è il limite superiore. La complessità spaziale è O(n) perché richiede una lista di tutti i numeri fino a n.
Ottimizzazioni:
Ci sono diverse ottimizzazioni possibili per il crivello di Eratostene, tra cui:
- Partire da p<sup>2</sup>: Invece di cancellare tutti i multipli di p, si può iniziare a cancellare da p<sup>2</sup>, poiché tutti i multipli inferiori a p<sup>2</sup> saranno già stati cancellati da numeri primi inferiori.
- Memorizzare solo i numeri dispari: Poiché tutti i numeri pari (eccetto 2) non sono primi, si può memorizzare solo i numeri dispari nella lista, riducendo la complessità spaziale.
- Crivello segmentato: Per numeri molto grandi, si può dividere l'intervallo in segmenti più piccoli e applicare il crivello a ciascun segmento separatamente.
Applicazioni:
Il crivello di Eratostene è un algoritmo utile per:
- Trovare tutti i numeri primi entro un determinato intervallo.
- Come passo preliminare in altri algoritmi che richiedono una lista di numeri primi.
- Come esempio di un algoritmo semplice ed efficiente per l'insegnamento dei concetti di base dell'informatica.
Argomenti importanti: